\onlyShort{\vspace{-0.4in}}
\section{Introduction} \label{sec:intro}
\onlyShort{\vspace{-0.1in}}
The importance, as well as the difficulty, of solving problems on hypergraphs was pointed out recently by Linial, in his Dijkstra award talk \cite{linial-talk}.
While standard graphs\footnote{Henceforth,
when we say a graph, we just mean a standard (simple) graph.} model {\em pairwise} interactions well,
 hypergraphs  can be used to model {\em multi-way} interactions. For example, social network interactions include several individuals as a group, biological interactions involve several entities (e.g., proteins) interacting at the same time, distributed systems can involve several agents working together, or multiple clients who share a server (e.g., a cellular base station), or multiple servers who share a client, or shared channels in a wireless network. In particular, hypergraphs are especially useful in modelling social networks (e.g., \cite{wasserman}) and
 wireless networks (e.g., \cite{avin}).
 %hypergraphs naturally arise, e.g., dominating set \cite{} and byzantine agreement \cite{}.
%shay: I am not familiar with these examples. Is it clear why a dominating set is an example of a hypergraph? are these citations such that they will increase the chances of the paper beyond the previous examples?
Unfortunately, as pointed out by Linial, much less is known for hypergraphs than for graphs.
The focus of this paper is studying the complexity of fundamental local
%!
symmetry breaking
problems in {\em hypergraphs}\footnote{Formally, a hypergraph $(V,F)$
consists of a set of (hyper)nodes $V$ and a collection $F$ of subsets of $V$; the sets that belong to $F$ are called  {\em hyperedges}.
The {\em dimension} of a hypergraph is the maximum number of hypernodes that belong to a hyperedge. Throughout, we will use $n$ for the number of nodes,
$m$ for the number of hyperedges,  and $\Delta$ for the degree of the hypergraph which is the maximum node degree (i.e., the maximum number of edges a node is in).
%(A hypergraph is {\em uniform}
%if all hyperedges consists of the same {\em number} of nodes.)
 A standard graph is a  hypergraph of dimension 2.}. A related goal is to utilize these hypergraph algorithms for solving (standard) graph problems.

%\danupon{I found this paragraph quite confusing. In particular, since I already know that the problem is local, it confuses me when you try to convince the readers that the problem could be global. I think other readers might face the same problem too.}
%
%Fundamental local symmetry breaking  problems such as Maximal Independent Set (MIS) and coloring have been studied extensively in (standard) graphs.
In the area of distributed computing for (standard) graphs,
%a major class of problems that was studied (extensively) is that of
fundamental local symmetry breaking problems such as Maximal Independent Set (MIS) and coloring have been studied extensively (see e.g., \cite{Luby86,Linial92,elkin-book,Pel00,kuhn-local} and the references therein).
%, and the importance of this sub area\danupon{subarea?} was recognized, e.g., recently by the 2013 Dijkstra prize \cite{dijkstra-laudatio}.
%Some very known examples to such problems are
%Maximal Independent Set (MIS) and coloring.
Problems such as MIS and coloring  are ``local'' in the sense
that a solution can be {\em verified} easily by purely local  means (e.g.,  each node  communicating only with its neighbors),
but the  solution itself  should satisfy a  global property
(e.g., in the case of coloring, every node in the graph should have a color different from its neighbors and the total number of colors is at most $\Delta + 1$, where $\Delta$ is the maximum node degree).
%but computing the solution seems to be a global task. That is, first, the collection of the choices made by individual nodes leads to a global property; second, the choices of different nodes depend on each other (e.g., if a node chooses to be in the MIS, its neighbors must choose not to be, which, in some cases, may force their neighbors to choose to be, and so forth).
Computing an MIS or coloring locally is non-trivial because of the difficulty of {\em symmetry breaking}: nodes have to decide on their choices  (e.g., whether they belong to the MIS or not) by only looking at a {\em small} neighbourhood around it. (In particular,
to get an algorithm running in $k$ rounds,
%This is the  difficulty of symmetry breaking and these problems capture the essence
%of symmetry breaking.
%Hence, for any given $k< D$, where $D$ is the graph diameter, it seems that the inclusion in the MIS of nodes whose distance from some node $v$ is larger (than $k$), seems to impact
%the question whether $v$ can be included. On the face of it, this means that sublinear algorithms may be impossible: clearly,
%to have an algorithm running in $k < D$ rounds for MIS,
each node $v$ has to make its decision by looking only
% within its $k$-neighborhood, i.e.,
at information on nodes within
distance $k$ from it.)
 % Given that, it was rather surprising that fast and rather local algorithms for such problems do exist. Indeed, some such algorithms are among the most celebrated results in distributed computing.
Some of the most celebrated results in distributed algorithms are  such fast localized algorithms.
In particular, $O(\log n)$-round (randomized) distributed algorithms are well-known for MIS \cite{Luby86} and $\Delta +1$-coloring \cite{elkin-book} in both the LOCAL and CONGEST distributed computing models \cite{Pel00}. 
%A pioneering deterministic algorithm in this area is the ``deterministic coin tossing'' \cite{cole-vishkin}.
%

Besides the interest in understanding the complexity of  fundamental problems,
the solutions to such localizable symmetry breaking problems had many obvious applications. Examples are scheduling (such as avoiding the collision of radio transmissions, see e.g. \cite{ephremides},
 \cite{chlamtac-kutten},
 or matching nodes such that each pair can communicate in parallel to the other pairs, see e.g. \cite{d2matching}), resource management (such as assigning clients to servers, see, e.g. \cite{azar-naor-rom}),
and even for obtaining $O(Diameter)$ solutions to global problems that cannot be solved locally, such as MST computation \cite{DBLP:journals/siamcomp/GarayKP98,KDOM}.

In contrast to graphs which have been extensively studied in the context of distributed algorithms,
% much less is known
%on the  complexity of fundamental distributed computing problems in hypergraphs. A reason for this is that
many problems become much more challenging in the context of hypergraphs. An outstanding example is the  MIS problem, whose local solutions for graphs were mentioned above.
% While the MIS problem admits a (non-trivial) $O(\log n)$ round
%algorithm in standard graphs (e.g., \cite{Luby}),
On the other hand, in hypergraphs (of arbitrary dimension) the complexity of MIS  is wide open. (In a hypergraph, an MIS is a maximal subset $I$ of hypernodes such that no subset of $I$ forms an hyperedge.)
Indeed, determining the parallel complexity (in the PRAM model) of the Maximal Independent Set (MIS) problem in hypergraphs (for arbitrary dimension) remains as one of the most important open problems in parallel computation; in particular, a key open problem is whether there exists a
polylogarithmic time PRAM algorithm \cite{karp-ram,BeameL90,Kelsen92}.   As discussed later, efficient CONGEST model distributed algorithms 
that uses simple local computations will also give efficient PRAM algorithms. 


%The focus of this paper is studying the complexity of fundamental local
%   %!
%symmetry breaking
%problems in {\em hypergraphs}.
%The motivation is two fold. First, a hypergraph is a natural generalization of the (standard) graph and serves as a useful model in many applications.  %shay: I think we talked already about motivation.

\onlyShort{\vspace{-0.15in}}
\subsection{Main Results}
\onlyShort{\vspace{-0.1in}}

%\danupon{This section is quite long and dense. It should help (although it's not crucial) to summarize the result somewhere, e.g. in a table. Also, there are so many parentheses.}

 %We study the distributed complexity of symmetry breaking in hypergraphs  by presenting
We present distributed (randomized) algorithms for a variety of fundamental problems under a natural distributed computing model for hypergraphs (cf. Section \ref{sec:prelim}). 

\paragraph	{Hypergraph MIS}
A main focus is the hypergraph MIS problem which has been the subject of extensive research in
the PRAM model  (see e.g., \cite{karp-ram,KarpUW88,Kelsen92,BeameL90,Luczak}).  We first show that MIS in hypergraphs (of arbitrary dimension) can be solved in  $O(\log^2 n)$ distributed rounds ($n$ is the number of nodes of the hypergraph) in the LOCAL  model (cf. Theorem \ref{thm:mis}).
We then present  an $O(\Delta^{\eps} \polylog n)$ round algorithm for finding a MIS in hypergraphs of arbitrary dimension in the CONGEST model,  where $\Delta$ is the maximum degree of the hypergraph %(i.e., the maximum number of hyperedges a node belongs to)
 and $\eps > 0$ is any small positive constant (we refer to Theorem \ref{thm:mis} for a precise statement of the bound). 
In the distributed computing model (both LOCAL and CONGEST), computation within a node is free; in one round, each node is allowed to compute any function of its current data. However, in our CONGEST model algorithms,  each processor will perform very simple computations (but this is not true in the LOCAL model). In particular, each step of any node $v$ can be simulated in $O(d_v)$  time by a single processor or in $O(\log m)$  time with $d_v$ processors.  Here, $d_v$ is the degree of
the node in the {\em server-client} computation model --- cf. Section \ref{sec:prelim};   $d_v = O(m)$, where $m$ is the number of hyperedges.  From these remarks, it follows that our algorithms can be simulated on the PRAM model to within an $O(\log m)$ factor slowdown using $O(m+n)$ processors.
Thus our CONGEST model algorithm also implies a  PRAM algorithm for hypergraph MIS running  in $O(\Delta^{\eps}\polylog n \log m)$ rounds using  $O(m+n)$ of processors for a hypergraph of arbitrary dimension. 

%shay: the following seems a repetition. some staff that was not said in the previous location, I moved there.
%In contrast to graphs which have been extensively studied in the context of distributed algorithms, much less is known
%on the  complexity of fundamental distributed computing problems in hypergraphs. A reason for this is that many problems become much more challenging %in the context of hypergraphs. An outstanding example is the MIS problem. While the MIS problem admits a (non-trivial) $O(\log n)$ round
%algorithm in standard graphs (e.g., \cite{Luby}), in hypergraphs (of arbitrary dimension) its complexity is wide open.
%Indeed, determining the parallel complexity (in the PRAM model) of the Maximal Independent Set (MIS) problem in hypergraphs (for arbitrary dimension) %remains as one of the most outstanding  open problems in parallel computation.

%The second motivation for studying hypergraphs is that they arise naturally in solving certain problems in  graphs.

\paragraph{Algorithms for standard graph problems using hypergraph MIS}
In addition to the importance of hypergraph MIS as a hypergraph problem, we outline its importance to solving several natural symmetry breaking problems in (standard) graphs too. For  the results discussed below, we assume the CONGEST model.

Consider first the following  graph  problem
called  the {\em restricted minimal dominating set (RMDS)} problem which arises as a key subproblem in other problems
that we discuss later. We are given a (standard) graph $G = (V,E)$ and a subset of nodes $R \subseteq V$, such
that  $R$ forms a dominating set in $G$ (i.e., every node $v \in V$ is either adjacent to $R$ or belongs to $R$).
It is required to find a {\em minimal} dominating set {\em in $R$} that dominates $V$. 
(The minimality means that no subset of the solution can dominate $V$; it is easy to verify the minimality condition locally.)
%For example, such a problem
%can arise if we want to minimally cover a set of clients (e.g., cell phones) by servers (cellular base stations).
Note that if $R$ is $V$ itself, the problem can be solved by finding a MIS of $G$, since a MIS is also a minimal dominating set (MDS); hence an $O(\log n)$ algorithm exists. However, if $R$ is some arbitrary proper subset of $V$ 
(such that $R$ dominates $V$), then
%finding a RMDS in $H$ is non-trivial; in fact,
%shay: I do not want to imply that Lubi's algorithm solves a trivial problem.
no  distributed algorithm running even in sublinear (in $n$) time (let alone polylogarithmic time) is known.
%\shay{before the current paper, not even algorithm in sublinear, insn't it? it seems better to state it that way} 
Using our hypergraph MIS algorithm, we design a  distributed algorithm for RMDS  running  in $O(\min\{\Delta^{\eps}\polylog n, n^{o(1)}\})$ rounds in the CONGEST model ($\Delta$ is the maximum node degree of the graph) --- cf., Section \ref{sec:rmds}.

% Why is the RMDS problem interesting?
RMDS arises naturally as the key subproblem in the solution of other  problems, in particular, the {\em balanced minimal dominating set (BMDS)} problem \cite{balanced-minimal}
%\cite{balanced-dominating} ====shay: is this the right citation?====
and the {\em minimal connected dominating set (MCDS)} problem. Given a (standard) graph, the BMDS problem (defined formally in Section \ref{sec:bmds})  asks for a minimal dominating set whose average degree is small with respect to the average degree of the graph; this has applications to load balancing and fault-tolerance \cite{balanced-minimal}.  It was shown that such a set exists and can be found using a {\em centralized} algorithm \cite{balanced-minimal}. Finding a fast distributed algorithm  was a key problem left open in \cite{balanced-minimal}. In Section \ref{sec:mcds}, we use our hypergraph MIS algorithm of Section~\ref{sec:hyper} to present an  $\tilde{O}(D+ \min\{\Delta^{\eps}, n^{o(1)}\})$ round algorithm (the notation $\tilde{O}$ hides a $\polylog n$ factor) for BMDS problem (in the CONGEST model), where
$D$ is the diameter (of the input standard graph) and $\Delta$ is the maximum node degree. 

The MCDS problem is a variant (similar to variants studied in the context of wireless networks, e.g. \cite{localized-cds}) of the well-studied
{\em minimum} connected dominating set problem (which is NP-hard) \cite{approx-min-connected,routing-min-connected}. 
%shay: I gave non theoretical citations since the second citation above has 800 citations, the first 260.
  In the MCDS problem, we require a dominating set that is connected and is {\em minimal} (i.e.,
no subset of the solution is a MCDS). In contrast to the approximate minimum connected dominating set problem
(i.e., finding a connected dominating set that is not too large compared to the optimal) which admits efficient distributed algorithms \cite{Dubhashi,ghaffari} (polylogarithmic run time algorithms are known
for both the LOCAL and CONGEST model for the unweighted case), we show that it is impossible to obtain an efficient distributed algorithm for MCDS. 
%The main difficulty is enforcing the minimality condition with respect to both domination and connectivity.   
 In Section \ref{sec:mcds}, we use our hypergraph MIS algorithm of Section \ref{sec:hyper}  as a subroutine to construct a distributed algorithm for MCDS that runs in time
$\tilde O(D (D\min\{\Delta^{\eps}, n^{o(1)}\} +\sqrt{n}) )$. We also show that $\tilde \Omega(D + \sqrt{n})$ is a lower bound
on the run time for any distributed  MCDS algorithm. The lower bound of $\tilde{\Omega}(D+\sqrt{n})$ for the MCDS problem is shown using the techniques
of Das Sarma et al. \cite{STOC11}. This lower bound holds even when $D=\polylog n$. In this case, our upper bound is tight up to a $\polylog n$ factor.
%We also show that $\Omega(D)$ is a {\em universal} lower bound for MCDS 
%; this bound applies also to randomized algorithms succeeding with at least some
 %constant probability and also holds in the LOCAL model. 

\paragraph{Algorithms for other hypergraph problems}
Besides MIS (and the above related standard graph problems), we also study distributed algorithms for coloring, maximal matching,   and maximal clique in hypergraphs\onlyLong{.}\onlyShort{ in the full paper.}  We show that a $\Delta+1$-coloring of a hypergraph (of any arbitrary dimension) can be computed in $O(\log n)$ rounds (this generalizes the result for standard graphs).  We also show that maximal matching in hypergraphs can be solved in $O(\log m)$ rounds.
%by reducing the problem to finding the MIS in the {\em line graph} of the hypergraph.
Maximal clique is a less-studied problem, even in the case of graphs, but nevertheless interesting.
Given a (standard) graph $G=(V,E)$,  a maximal clique (MC) $L$ is subset of $V$ such that $L$ is a clique in $G$
and is maximal (i.e., it is not contained in a bigger clique). MC is related to MIS since any MIS in the complement graph $G^c$ is an MC in $G$.
For a hypergraph, one can define an MC with respect to the server graph (cf. Section \ref{sec:prelim}). 
Finding MC has applications in finding a {\em non-dominated coterie} in quorum systems \cite{makino}.
We show that an MC in a hypergraph can be found in  $O(D+\dimension \log n)$ rounds, where $\dimension$ is the dimension of the hypergraph and $n$ is the number of nodes. All the above results hold in the CONGEST model as well. 
%It can be noted that a MIS in the complement graph of $G$ is a MC in $G$.

We also show that $\Omega(D)$ is a {\em universal} lower bound for MCDS as well as for maximal clique and spanning tree problems, i.e., it applies essentially to all graphs. \onlyShort{These are shown in the full paper.}


\onlyShort{\vspace{-0.15in}}
\subsection{Technical Overview and Other Related Work}
\onlyShort{\vspace{-0.1in}}
We study two natural network models for computing with hypergraphs --- the {\em server-client} model
and the {\em vertex-centric} models (cf. Section \ref{sec:prelim}). The server-client model is commonly used in packing and covering problems such as set cover and packing LPs (e.g., \cite{Suomela13,AstrandS10,PapadimitriouY93,KuhnMW06,BartalBR97,Kuhn2005-thesis}).  It is also a natural model for the facility location problem (e.g., \cite{MoscibrodaW05,PanditP09}).  The vertex-centric model was considered in, e.g., \cite{KoufogiannakisY11}. 
%
%We note that while these models might not be equal to the physical structure of a real-world distributed system, in many applications algorithms in these models can be straightforwardly simulated in actual networks.\danupon{E.g. \cite{Suomela13,Kuhn2005-thesis}}
%While these models might not be equal to the physical structure of a real-world distributed system, they are useful as we can efficiently simulate algorithms in these models in some applications (such as those in \Cref{{sec:applications}). 
%
%We note that the two models have the same power when the underlying network is modeled by the LOCAL model (i.e. there is no bound on the message size), but they might be different in power for the case of CONGEST model (see, e.g., \cite{KuhnMW06}). 
%but this might not be the case when the network is modeled by the CONGEST model. 
%
%Nevertheless, our algorithmic results apply to both server-client and vertex-centric models (except the one on maximal matching). 
Our algorithmic results apply to both models (except the one on maximal matching). 

The distributed MIS problem on hypergraphs is significantly more challenging than that on (standard) graphs.
Simple variants/modifications of the distributed algorithms on graphs (e.g.,  Luby's algorithm and its variants \cite{Luby86,MetivierRSZ11,Pel00})  do not seem to work for higher dimensions, even
for hypergraphs of dimension 3. For example, running Luby's algorithm or its permutation variant \cite{Luby86} on a (standard) graph by replacing each hyperedge with a clique does not work --- in the graph there can be only one
node in the MIS, whereas in the hypergraph all nodes of the clique, except one, can be in the MIS. 
It has been conjectured by Beame and Luby \cite{BeameL90} that a generalisation of the permutation variant of an algorithm due to Luby \cite{Luby86} can give
a $\polylog(m+n)$ run time in the PRAM model, but this has not been proven so far (note that this bound itself can be large, since $m$ can be exponential in $n$). 
%
%We also note that in contrast to the above difficulty, many algorithms on standard graphs can be easily generalized to hypergraphs; e.g., vertex cover algorithms can usually be extended to 

\danupon{Papers that are very related to us but I don't know where to mention it is \cite{AstrandS10} where they approximate set cover. They also cite a few other papers related to this problem.}

%case of symmetry breaking problems, algorithms 

Our distributed hypergraph MIS algorithm (Section \ref{sec:hyper}) consists of several ingredients. A key ingredient is the {\em decomposition lemma} (cf. Lemma \ref{thm:decomposition congest}) that shows that the problem can be reduced to solving a MIS problem in a low diameter network.  The lemma is essentially an application of the {\em network decomposition} algorithm of Linial and Saks \cite{LinialS93}.  This applies to the CONGEST model as well --- the main task in the proof is to show that the Linial-Saks decomposition works for (both) the hypergraph models in the CONGEST setting. The polylogarithmic run time bound for the LOCAL model follows easily 
from the decomposition lemma. However, this approach fails in the CONGEST model, since it involves collecting a lot of information at some nodes. The next ingredient is to show how the PRAM algorithm of Beame and Luby \cite{BeameL90} can be simulated efficiently in the distributed setting; this we show is
possible in a low diameter graph.  Kelsen's analysis \cite{Kelsen92} of Beame-Luby's algorithm (which shows a polylogarithmic time bound  in the PRAM model for {\em constant} dimension hypergraphs) immediately gives a polylogarithmic round algorithm in the CONGEST
model for a hypergraph of {\em constant} dimension.  To obtain the $\tilde{O}(\Delta^{\eps})$ algorithm  (for any constant $\eps > 0$) for 
a hypergraph of {\em arbitrary} dimension in the CONGEST model, we use another 
ingredient: we generalize a theorem of Turan  (cf. Theorem \ref{thm:Turan}) for hypergraphs --- this shows that a hypergraph of low average degree has a  {\em large} independent set. We show further that such a large independent set can be found  when the network diameter is $O(\log n)$.  Combining this theorem
with the analysis of Beame and Luby's algorithm gives the result for the CONGEST model for any dimension. Our CONGEST model algorithm, as pointed out earlier, also implies a $\tilde{O}(\Delta^{\eps})$ round algorithm for the PRAM model.
 Recently, independently of our result,
 Bercea et al.\cite{aravind2} use a similar approach to obtain an improved algorithm for the PRAM model. In particular, they improve Kelsen's analysis of Beame-Luby algorithm to apply also for slightly {\em super-constant} dimension. This improved analysis of Kelsen also helps us
 in obtaining a slightly better bound (cf. Theorem \ref{thm:mis}).
 
We apply our hypergraph  MIS algorithm  to solve two key problems --- BMDS and MCDS. 
The BMDS problem was posed in Harris et al. \cite{balanced-minimal}, but no efficient distributed algorithm was known.
A key bottleneck was solving the RMDS problem which appears as a subroutine in solving BMDS.
In the current paper, we circumvent this bottleneck by treating the RMDS problem as a problem on hypergraphs.
\begin{comment}
We can view RMDS
as a hypergraph problem. To see this, it  is useful to define a hypergraph  using the following {\em server-client  bipartite graph model $B=(S,C)$}: the server set $S$ represents the nodes of the hypergraph and the client set $C$
represents the  hyperedges; an edge is present between a server $s$  and a client $c$ if and only if node $s$
belongs to the hyperedge $c$. Given an instance of the RMDS problem, we take the server set as $R$   and
the client set as $V$ and an edge is present between a server and a client if  the server is adjacent to (or is the same as) the client in the given graph $G$. Solving the RMDS problem now reduces to solving the {\em minimal hitting set (MHS)} (same as the {\em minimal vertex cover(MVC)}) 
problem\footnote{A MHS (same as MVC) of a hypergraph  is a minimal subset $H$ of hypernodes that such that $H \cap e \neq \emptyset$, for every
hyperedge $e$ of the hypergraph. Note that the complement of a MHS is a MIS.}  in this hypergraph (cf., Section \ref{sec:rmds}).  Since a MHS is just the complement of the MIS (in the server set), this reduces
to solving MIS problem in a hypergraph.
\end{comment}


The MCDS problem, to the best of our knowledge, has not been considered before and seems significantly
harder to solve in the distributed setting compared to the more well-studied approximate version of the connected dominating set problem \cite{Dubhashi,ghaffari}. The key difficulty is being {\em minimal} with respect to {\em both}
connectivity and domination. We use a layered approach to the problem, by first constructing a breadth-first tree (BFS) and then adding nodes to the MCDS, level by level of the tree (starting with the leaves).
\onlyLong{
We make sure that nodes added to the MCDS in level $i$ dominates the nodes in level $i+1$ and is also minimal. To be minimal with respect to connectivity we cluster nodes that are in MCDS at level $i+1$ by connected components and treat these as super-nodes. To minimally dominate these super nodes we use the hypergraph MIS algorithm; however there is a technical difficulty of simulating
the hypergraph algorithm on super-nodes. We show that such a simulation can be done efficiently by reducing the dimension of the constructed hypergraph (\onlyLong{cf. Lemma \ref{lem:logn}}\onlyShort{cf. Lemma 4.4 in the full paper in Appendix}) which show that hypergraph MIS on a hypergraph of arbitrary dimension can be reduced to solving a equivalent problem in 
a hypergraph of $\polylog(m+n)$ dimension with only $O(\log n)$ factor slow down. 
}
%
%The fact that we need
%to find connected components along with applying the hypergraph MIS algorithm 
%gives an overall time of $\tilde O(D (D\Delta^{\eps} +\sqrt{n}) )$.
%






\iffalse
\subsection{Organization}
The rest of the paper is organized as follows. Section \ref{sec:prelim}  discusses preliminaries including the  computation 
model and notations used throughout the paper. Section \ref{sec:hyper} presents our hypergraph MIS algorithms. 
 Section \ref{sec:applications} presents applications of our hypergraph algorithms
to the standard graph setting.
Section \ref{sec:other} presents hypergraph algorithms for other problems.
 Section \ref{sec:lb} presents lower bounds. Section \ref{sec:conc} discusses some implications
of our work and concludes.
\fi


 
